package twobranchTree.issymmetirc;

import java.util.LinkedList;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;
/**
 * @Date 2020/2/23
 * @author 王光浩
 * @Thinking 使用迭代方法。
 * 			 复杂度分析：时间复杂度O（n/2），空间复杂度O（n)
 */
public class MyMethodOne {
	public boolean isSymmetric(TreeNode root) {
		if(root==null || (root.left==null && root.right==null))return true;
		LinkedList<TreeNode> left=new LinkedList<TreeNode>(); //保存左子树节点
		LinkedList<TreeNode> right=new LinkedList<TreeNode>();//保存右子树节点
		if(root.left!=null)left.add(root.left);
		if(root.right!=null)right.add(root.right);
		//对左右子树同时进行前序遍历
		while(!left.isEmpty() && !right.isEmpty()) {
			TreeNode leftnode=left.pollFirst();
			TreeNode rightnode=right.pollFirst();
			if(leftnode.val!=rightnode.val)return false; //节点值不相同
			//将左子树的右节点，右子树的左节点加入队列中
			if(leftnode.right!=null && rightnode.left!=null) {
				left.add(leftnode.right);
				right.add(rightnode.left);
			}
			else if(leftnode.right==null && rightnode.left==null) {}
			else    //节点不对称
				return false;
			//将左子树的左节点，右子树的右节点加入队列中
			if(leftnode.left!=null && rightnode.right!=null) {
				left.add(leftnode.left);
				right.add(rightnode.right);
			}
			else if(leftnode.left==null && rightnode.right==null) {}
			else    //节点不对称
				return false;
		}
		//最后都为空则返回true
		return left.size()==right.size();
	}
}
